import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Test34 {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        Map<Long,List<Integer>> hash = new HashMap<>();
        for(int i = 0;i < n;i++) {
            if(!hash.containsKey((long)nums[i])) {
                List<Integer> list = new ArrayList<>();
                hash.put((long)nums[i],list);
            }
            hash.get((long)nums[i]).add(i);
        }
        int count = 0;
        int[][] dp = new int[n][n];
        for(int j = 2;j < n;j++) {
            for(int i = 1;i < j;i++) {
                long a = (long)2 * nums[i] - nums[j];
                if(hash.containsKey(a)) {
                    for(int k : hash.get(a)) {
                        if(k < i) {
                            dp[i][j] += dp[k][i] + 1;

                        }else {
                            break;
                        }

                    }
                }
                count += dp[i][j];
            }
        }
        return count;
    }
}
